#include "evaluate.h"

extern int gridUnit;
extern int x_gridNum;
extern int y_gridNum;
extern int numBins;
extern ckt this_ckt;
extern double HPWL, penalty, displacement, max_displacement, targUt;
extern string directory;
extern vector<double> util_array;


void fixNet(ckt & ptrckt, node & this_node)
{
	for(unsigned i = 0; i < this_node.pins.size(); i++)
	{
		int netID = this_node.pins[i].pin2net;
		net & this_net = ptrckt.nets[netID];
		
		double netMaxX = ptrckt.lx;
		double netMinX = ptrckt.rx;
		double netMaxY = ptrckt.by;
		double netMinY = ptrckt.ty;

		for(unsigned j = 0; j < this_net.nodeIds.size(); j++)
		{
			node & cur_node = ptrckt.nodes[ ptrckt.nets[netID].nodeIds[j] ];
			double x_pinloc = cur_node.x_coord + 0.5 * cur_node.width + this_net.x_offset[j];
			double y_pinloc = cur_node.y_coord + 0.5 * cur_node.height + this_net.y_offset[j];

			if(j == 0)
			{
				netMaxX = netMinX = x_pinloc;
				netMaxY = netMinY = y_pinloc;
			}
			else
			{
				netMaxX = max(netMaxX, x_pinloc);
				netMinX = min(netMinX, x_pinloc);
				netMaxY = max(netMaxY, y_pinloc);
				netMinY = min(netMinY, y_pinloc);
			}
		}
		ptrckt.nets[netID].max_X = netMaxX; 
		ptrckt.nets[netID].min_X = netMinX;
		ptrckt.nets[netID].max_Y = netMaxY; 
		ptrckt.nets[netID].min_Y = netMinY;
 	}
}

void fixRow(ckt & ptrckt, tinyRow & this_row)
{
	if(this_row.ID % x_gridNum == x_gridNum - 1 || this_row.NodeID.size() == 0)
		return;
	if(this_row.rx > this_row.r_end)
	{
		int max_right_coord = 0;
		for(int i = 0; i < this_row.NodeID.size(); i++)
		{
			node & this_node = ptrckt.nodes[this_row.NodeID[i]];
			if(this_node.x_coord + this_node.width > max_right_coord)
				max_right_coord = this_node.x_coord + this_node.width;

			if(max_right_coord <= this_row.r_end)
			{
				this_row.rx = this_row.r_end;
				ptrckt.tinyRows[this_row.ID + 1].lx = this_row.r_end;
			}
			else
			{
				this_row.rx = max_right_coord;
				ptrckt.tinyRows[this_row.ID + 1].lx = max_right_coord;
			}
		}
	}
	return;
}

bool compareNodeID::operator()(int a, int b)
{
	return (this_ckt.nodes[a].x_coord < this_ckt.nodes[b].x_coord);
}

bool space_query(ckt & ptrckt, node & this_node, tinyRow & this_row, int x, query & answer)
{
	assert(this_row.isValid);
	assert(x >= 0);
	assert(x <= this_row.rx - this_row.lx);

	vector<int> & node_array = this_row.NodeID;
	sort(node_array.begin(), node_array.end(), compareNodeID());


	if(node_array.size() == 0)
	{
		answer.cellID_right = -1;
		answer.cellID_left = -1;
		answer.cellID_second_left = -1;
		answer.cellID_second_right = -1;
		answer.space = this_row.rx - this_row.lx;
		answer.space_left = -1;
		answer.space_right = -1;
		answer.available_space = this_row.rx - this_row.lx;
		return true;
	}
	else // At least one cell in this tinyRow
	{
		int absolute_x = this_row.lx + x;
		int i;
		for(i = 0; i < node_array.size(); i++)
		{
			node & node_right = ptrckt.nodes[node_array[i]];
			if(absolute_x <= (int)node_right.x_coord) // Found a node on its right
				break;
		}
		
		answer.cellID_right = -1;
		answer.cellID_left = -1;
		answer.cellID_second_left = -1;
		answer.cellID_second_right = -1;
		answer.space = this_row.rx - this_row.lx;
		answer.space_left = -1;
		answer.space_right = -1;
		answer.available_space = this_row.rx - this_row.lx;
		int right_x = this_row.rx;
		int left_x = this_row.lx;

		// First deal with left side
		if(i == 0)
		{
			// Do nothing, everything set as above
		}
		else if(i == 1)
		{
			answer.cellID_left = this_row.NodeID[0];
			answer.space_left = ptrckt.nodes[node_array[0]].x_coord - this_row.lx;
			assert(answer.space_left >= 0);
			left_x = ptrckt.nodes[node_array[0]].x_coord + ptrckt.nodes[node_array[0]].width;
			assert(left_x >= 0);
		}
		else // More than one cell on its left
		{
			answer.cellID_left = this_row.NodeID[i - 1];
			answer.cellID_second_left = this_row.NodeID[i - 2];
			node & left_cell = ptrckt.nodes[node_array[i - 1]];
			node & second_left_cell = ptrckt.nodes[node_array[i - 2]];
			assert(left_cell.x_coord >= second_left_cell.x_coord + second_left_cell.width);
			assert(second_left_cell.x_coord >= this_row.lx);
			answer.space_left = left_cell.x_coord - (second_left_cell.x_coord + second_left_cell.width);
			assert(answer.space_left >= 0);
			left_x = left_cell.x_coord + left_cell.width;
			assert(left_x >= 0);
		}

		// Then deal with right side
		if(i == node_array.size())
		{
			// Do nothing, everything set as above
			assert(i != 0);
		}
		else if(i == node_array.size() - 1) // Only one cell on the right
		{
			answer.cellID_right = this_row.NodeID[i];
			answer.space_right = this_row.rx - (ptrckt.nodes[node_array[i]].x_coord + ptrckt.nodes[node_array[i]].width);
			assert(answer.space_right >= 0);
			right_x = ptrckt.nodes[node_array[i]].x_coord;
		}
		else // More than one cell on its right
		{
			answer.cellID_right = this_row.NodeID[i];
			answer.cellID_second_right = this_row.NodeID[i + 1];
			assert(i + 1 < node_array.size());
			node & right_cell = ptrckt.nodes[node_array[i]];
			node & second_right_cell = ptrckt.nodes[node_array[i + 1]];
			
			assert(second_right_cell.x_coord + second_right_cell.width <= this_row.rx);
			assert(right_cell.x_coord + right_cell.width <= second_right_cell.x_coord);
			answer.space_right = second_right_cell.x_coord - (right_cell.x_coord + right_cell.width);
			assert(answer.space_right >= 0);
			right_x = right_cell.x_coord;
		}

		answer.space = right_x - left_x;
		assert(answer.space >= 0);

		answer.available_space = answer.space;
		if(answer.cellID_left != -1 && !ptrckt.nodes[answer.cellID_left].isFixed)
			answer.available_space += answer.space_left;
		else
			answer.space_left = -1;

		if(answer.cellID_right != -1 && !ptrckt.nodes[answer.cellID_right].isFixed)
			answer.available_space += answer.space_right;
		else
			answer.space_right = -1;

		assert(answer.available_space >= answer.space);

		return true;
	}
}

bool insert2site(ckt & ptrckt, node & this_node, tinyRow & dest_row, int x)
{	
	assert(!this_node.isFixed);
	assert(dest_row.isValid);
	assert(x >= 0);
	assert(x <= dest_row.rx);

	query answer;
	if(space_query(ptrckt, this_node, dest_row, x, answer)) // Dummy Insert
	{
		if(answer.space >= this_node.width) // Can insert directly
		{
			if(answer.cellID_left == -1) // No cell on the left of x
			{
				this_node.x_coord = dest_row.lx;
				this_node.y_coord = dest_row.y;
			}
			else // At least one cell on the left of x
			{
				this_node.x_coord = ptrckt.nodes[answer.cellID_left].x_coord + ptrckt.nodes[answer.cellID_left].width;
				this_node.y_coord = dest_row.y;
				assert(this_node.x_coord >= dest_row.lx);
			}

			// Can be more efficient
			dest_row.NodeID.push_back(this_node.ID);
			sort(dest_row.NodeID.begin(), dest_row.NodeID.end(), compareNodeID());
			fixNet(ptrckt, this_node);

			move_node_in_row(ptrckt, this_node, this_node.x_coord, this_node.x_coord + answer.space - this_node.width);
			sort(dest_row.NodeID.begin(), dest_row.NodeID.end(), compareNodeID());
			return true;
		}
		else if(answer.available_space >= this_node.width) // Need to move adjacent cells
		{
			if(answer.space_left == -1) // right space must exist
			{
				assert(answer.space_right != -1);
				assert(answer.cellID_right != -1);
				node & right = ptrckt.nodes[answer.cellID_right];
				
				
				right.x_coord += answer.space_right;
				assert(right.x_coord + right.width <= dest_row.rx);
				fixNet(ptrckt, right);

				if(answer.cellID_left == -1)
				{
					this_node.x_coord = dest_row.lx;
					this_node.y_coord = dest_row.y;
					assert(ptrckt.nodes[dest_row.NodeID[0]].x_coord >= dest_row.lx + this_node.width);
					assert(dest_row.lx >= dest_row.l_end);
				}
				else
				{
					assert(ptrckt.nodes[answer.cellID_left].isFixed);
					this_node.x_coord = ptrckt.nodes[answer.cellID_left].x_coord + ptrckt.nodes[answer.cellID_left].width;
					this_node.y_coord = dest_row.y;
				}
				fixNet(ptrckt, this_node);
				dest_row.NodeID.push_back(this_node.ID);
				sort(dest_row.NodeID.begin(), dest_row.NodeID.end(), compareNodeID());

				// move_node_in_row(ptrckt, this_node, this_node.x_coord, right.x_coord - this_node.width);
				// move_node_in_row(ptrckt, right, this_node.x_coord + this_node.width, right.x_coord);

				/* Position optimization */
				tinyRow fake_row;
				fake_row.lx = this_node.x_coord;
				fake_row.rx = right.x_coord + right.width;
				fake_row.y = dest_row.y;
				fake_row.l_end = dest_row.l_end;
				fake_row.r_end = dest_row.r_end;
				fake_row.isValid = true;
				fake_row.NodeID.push_back(this_node.ID);
				fake_row.NodeID.push_back(right.ID);
				place_tinyRow_DP(ptrckt, fake_row);
				//sort(dest_row.NodeID.begin(), dest_row.NodeID.end(), compareNodeID());
				return true;
			}
			else if(answer.space_right == -1) // left space must exist
			{
				node & left = ptrckt.nodes[answer.cellID_left];
				assert(!left.isFixed);
				assert(answer.space + answer.space_left >= this_node.width);

				left.x_coord -= answer.space_left;
				assert(left.x_coord >= dest_row.lx);
				fixNet(ptrckt, left);

				this_node.x_coord = left.x_coord + left.width;
				this_node.y_coord = dest_row.y;
				fixNet(ptrckt, this_node);
				dest_row.NodeID.push_back(this_node.ID);
				sort(dest_row.NodeID.begin(), dest_row.NodeID.end(), compareNodeID());

				// if(answer.cellID_right != -1) // right cell is fixed
				// {
				// 	move_node_in_row(ptrckt, this_node, left.x_coord + left.width,
				// 		ptrckt.nodes[answer.cellID_right].x_coord - this_node.width);
				// 	move_node_in_row(ptrckt, left, left.x_coord, this_node.x_coord - left.width);
				// }
				// else // no cells on the right
				// {
				// 	move_node_in_row(ptrckt, this_node, left.x_coord + left.width, dest_row.rx - this_node.width);
				// 	move_node_in_row(ptrckt, left, left.x_coord, this_node.x_coord - left.width);
				// }

				/* Position optimization */
				tinyRow fake_row;
				fake_row.lx = left.x_coord;
				if(answer.cellID_right != -1)
					fake_row.rx = ptrckt.nodes[answer.cellID_right].x_coord;
				else
					fake_row.rx = dest_row.rx;
				fake_row.y = dest_row.y;
				fake_row.l_end = dest_row.l_end;
				fake_row.r_end = dest_row.r_end;
				fake_row.isValid = true;
				fake_row.NodeID.push_back(left.ID);
				fake_row.NodeID.push_back(this_node.ID);
				place_tinyRow_DP(ptrckt, fake_row);

				//sort(dest_row.NodeID.begin(), dest_row.NodeID.end(), compareNodeID());
				return true;
			}
			else // both left and right space exist and movable
			{
				assert(answer.cellID_left >= 0);
				assert(answer.cellID_right >= 0);
				node & left = ptrckt.nodes[answer.cellID_left];
				node & right = ptrckt.nodes[answer.cellID_right];

				left.x_coord -= answer.space_left;
				assert(left.x_coord >= dest_row.lx);
				fixNet(ptrckt, left);

				right.x_coord += answer.space_right;
				assert(right.x_coord + right.width <= dest_row.rx);
				fixNet(ptrckt, right);

				this_node.x_coord = left.x_coord + left.width;
				this_node.y_coord = dest_row.y;
				assert(this_node.x_coord + this_node.width <= right.x_coord);
				fixNet(ptrckt, this_node);
				dest_row.NodeID.push_back(this_node.ID);
				sort(dest_row.NodeID.begin(), dest_row.NodeID.end(), compareNodeID());

				// move_node_in_row(ptrckt, this_node, left.x_coord + left.width, right.x_coord - this_node.width);
				// move_node_in_row(ptrckt, left, left.x_coord, this_node.x_coord - left.width);
				// move_node_in_row(ptrckt, right, this_node.x_coord + this_node.width, right.x_coord);

				/* Position optimization */
				tinyRow fake_row;
				fake_row.lx = left.x_coord;
				fake_row.rx = right.x_coord + right.width;
				fake_row.y = dest_row.y;
				fake_row.l_end = dest_row.l_end;
				fake_row.r_end = dest_row.r_end;
				fake_row.isValid = true;
				fake_row.NodeID.push_back(left.ID);
				fake_row.NodeID.push_back(this_node.ID);
				fake_row.NodeID.push_back(right.ID);
				place_tinyRow_DP(ptrckt, fake_row);
				//sort(dest_row.NodeID.begin(), dest_row.NodeID.end(), compareNodeID());
				return true;	
			}
		}	
	}
	return false;
}

// When assigned a tinyRow to be inserted, this function automatically finds a good place to insert
int insert2tinyRow(ckt & ptrckt, node & this_node, tinyRow & dest_row, int threshold)
{
	if(this_node.isFixed)
		return -1;

	int best_x = -1;
	int best_reduction = threshold;
	int x = this_node.x_coord; // Original x
	int y = this_node.y_coord; // Original y
	int i;
	query answer;

	// Strategy: Only examine the left end of each blank space
	if(space_query(ptrckt, this_node, dest_row, 0, answer) && answer.space >= this_node.width)
	{	
		int reduction = delta_HPWL(ptrckt, this_node.ID, dest_row.lx - x, dest_row.y - y);
		if(reduction < best_reduction)
		{
			best_reduction = reduction;
			best_x = 0;
		}
	}
	for(i = 0; i < dest_row.NodeID.size(); i++)
	{
		int current_x = ptrckt.nodes[dest_row.NodeID[i]].x_coord + ptrckt.nodes[dest_row.NodeID[i]].width - dest_row.lx;
		
		if(space_query(ptrckt, this_node, dest_row, current_x, answer))
		{	
			if(answer.space >= this_node.width) // Preferred way
			{
				int reduction = delta_HPWL(ptrckt, this_node.ID, current_x + dest_row.lx - x, dest_row.y - y);
				if(reduction < best_reduction)
				{
					best_reduction = reduction;
					best_x = current_x;
				}
			}
			else if(answer.available_space >= this_node.width) // Not preferred
			{
				int reduction = delta_HPWL(ptrckt, this_node.ID, current_x + dest_row.lx - x, dest_row.y - y) 
					+ this_node.width - answer.space;
				if(reduction < best_reduction)
				{
					best_reduction = reduction;
					best_x = current_x;
				}
			}	
		}
	}
	return best_x;
}

bool move_node_in_row(ckt & ptrckt, node & this_node, int left_bound, int right_bound)
{
	int best_move = 0;
	int best_reduction = 0;
	for(int move = left_bound - this_node.x_coord; move <= right_bound - this_node.x_coord; move++)
	{
		if(move == 0)
			continue;
		int reduction = delta_HPWL(ptrckt, this_node.ID, move, 0);
		if(reduction < best_reduction)
		{
			best_move = move;
			best_reduction = reduction;
		}
	}
	if(best_reduction < 0)
	{
		this_node.x_coord += best_move;
		fixNet(ptrckt, this_node);
		return true;
	}
	return false;
}

bool move_node_in_row(ckt & ptrckt, node & this_node, int left_bound, int right_bound, int step)
{
	int best_move = 0;
	int best_reduction = 0;
	for(int move = left_bound - this_node.x_coord; move <= right_bound - this_node.x_coord; move += step)
	{
		if(move == 0)
			continue;
		int reduction = delta_HPWL(ptrckt, this_node.ID, move, 0);
		if(reduction < best_reduction)
		{
			best_move = move;
			best_reduction = reduction;
		}
	}
	if(best_reduction < 0)
	{
		this_node.x_coord += best_move;
		fixNet(ptrckt, this_node);
		return true;
	}
	return false;
}


struct element
{
	double cost;
	int option;
};

struct net_bound
{
	double left_fixed_x;
	double right_fixed_x;
	int left_movable_ID;
	int right_movable_ID;
};

map<int, net_bound> net_map;
set<int> node_ID;
element table[100][150];
int prefix_width[100];
int node_width[100];

void place_tinyRow_DP(ckt & ptrckt, tinyRow & this_row) // All cells movable
{
	int size = this_row.NodeID.size();
	int right_bound = this_row.rx - this_row.lx - ptrckt.nodes[this_row.NodeID[size - 1]].width;

	/* Array Initialization */
	for(int i = 0; i < size; i++)
	{
		for(int j = 0; j < this_row.rx - this_row.lx; j++)
		{
			table[i][j].cost = -1;
			table[i][j].option = 0;
		}
	}
	memset(prefix_width, 0, sizeof(prefix_width));
	memset(node_width, 0, sizeof(node_width));
	
	/* Set up node ID set */
	node_ID.clear();
	for(int i = 0; i < size; i++)
	{
		node_ID.insert(this_row.NodeID[i]);
	}

	/* Set up net map and node set */
	net_map.clear();
	map<int, net_bound>::iterator map_it;
	for(int i = 0; i < size; i++)
	{
		node & this_node = ptrckt.nodes[this_row.NodeID[i]];
		for(int j = 0; j < this_node.pins.size(); j++)
		{
			int net_ID = this_node.pins[j].pin2net;
			map_it = net_map.find(net_ID);
			if(map_it != net_map.end())
			{
				// update the right_movable_ID of current net
				(map_it->second).right_movable_ID = this_node.ID; 
			}
			else // Need to establish a new entry
			{
				double left_fixed_x = -1;
				double right_fixed_x = -1;
				int left_movable_ID = -1;
				int right_movable_ID = -1;
				net & this_net = ptrckt.nets[net_ID];
				for(int k = 0; k < this_net.nodeIds.size(); k++)
				{
					set<int>::iterator it;
					it = node_ID.find(this_net.nodeIds[k]);
					if(it == node_ID.end()) // fixed node
					{
						node & fixed_node = ptrckt.nodes[this_net.nodeIds[k]];
						double pin_loc = fixed_node.x_coord + 0.5 * fixed_node.width + this_net.x_offset[k];
						if(left_fixed_x == -1)
						{
							left_fixed_x = pin_loc;
						}
						else
						{
							if(pin_loc < left_fixed_x)
								left_fixed_x = pin_loc;
						}
						if(right_fixed_x == -1)
						{
							right_fixed_x = pin_loc;
						}
						else
						{
							if(pin_loc > right_fixed_x)
								right_fixed_x = pin_loc;
						}
					}	
					else // movable node
					{
						if(left_movable_ID == -1 && right_movable_ID == -1)
						{
							left_movable_ID = right_movable_ID = this_net.nodeIds[k];
						}
						else // left_movable_ID != -1 && right_movable_ID != -1
						{
							if(ptrckt.nodes[this_net.nodeIds[k]].x_coord < ptrckt.nodes[left_movable_ID].x_coord)
								left_movable_ID = this_net.nodeIds[k];
							if(ptrckt.nodes[this_net.nodeIds[k]].x_coord > ptrckt.nodes[right_movable_ID].x_coord)
								right_movable_ID = this_net.nodeIds[k];
						}
					}				
				}
				net_bound temp = {left_fixed_x, right_fixed_x, left_movable_ID, right_movable_ID};
				net_map.insert(make_pair(net_ID, temp));
			}
		}
	}
	
	for(int i = 0; i < size; i++)
	{
		node_width[i] = ptrckt.nodes[this_row.NodeID[i]].width;
		prefix_width[i + 1] = prefix_width[i] + node_width[i];
	}
	// Calculate
	placement_cost(ptrckt, this_row, size - 1, right_bound);

	int index = size - 1;
	int x = this_row.rx - this_row.lx;

	while(index >= 0)
	{
		x -= node_width[index];
		while(table[index][x].option == 1)
			x--;
		ptrckt.nodes[this_row.NodeID[index]].x_coord = x + this_row.lx;
		fixNet(ptrckt, ptrckt.nodes[this_row.NodeID[index]]);
		index--;
	}
}

double cost(ckt & ptrckt, tinyRow & this_row, int i, int x)
{
	double cost = 0;
	map<int, net_bound>::iterator map_it;
	node & this_node = ptrckt.nodes[this_row.NodeID[i]];
	for(int j = 0; j < this_node.pins.size(); j++)
	{
		int net_ID = this_node.pins[j].pin2net;
		map_it = net_map.find(net_ID);
		if((map_it->second).left_movable_ID == this_node.ID)
		{
			double pin_x_coord = this_row.lx + x + this_node.width * 0.5 + this_node.pins[j].x_offset;
			if((map_it->second).left_fixed_x == -1)
				cost += this_row.rx - pin_x_coord;
			else if(pin_x_coord < (map_it->second).left_fixed_x)
				cost += (map_it->second).left_fixed_x - pin_x_coord;				
		}
		if((map_it->second).right_movable_ID == this_node.ID)
		{
			double pin_x_coord = this_row.lx + x + this_node.width * 0.5 + this_node.pins[j].x_offset;
			if((map_it->second).right_fixed_x == -1)
				cost += pin_x_coord - this_row.lx;
			else if(pin_x_coord > (map_it->second).right_fixed_x)
				cost += pin_x_coord - (map_it->second).right_fixed_x;
		}
	}
	return cost;
}

double placement_cost(ckt & ptrckt, tinyRow & this_row, int i, int x)
{
	if(i < 0)
		return 0;

	if(table[i][x].cost != -1) // Already calculated
	{
		return table[i][x].cost;
	}

	if(x == prefix_width[i])
	{
		table[i][x].option = 2;
		table[i][x].cost = placement_cost(ptrckt, this_row, i - 1, x - node_width[i - 1]) + cost(ptrckt, this_row, i, x);
		return table[i][x].cost;
	}
	else
	{
		assert(x > prefix_width[i]);

		double cost1 = placement_cost(ptrckt, this_row, i, x - 1);
		double cost2 = placement_cost(ptrckt, this_row, i - 1, x - node_width[i - 1]) + cost(ptrckt, this_row, i, x);

		if(cost1 >= cost2)
		{
			table[i][x].cost = cost2;
			table[i][x].option = 2; 
			return cost2;
		}
		else
		{
			table[i][x].cost = cost1;
			table[i][x].option = 1;
			return cost1;
		}
		
	}
}

/* Find the best relative positions for two consecutive cells */
int bi_swap(ckt & ptrckt, tinyRow & this_row, int index)
{
	node & node1 = ptrckt.nodes[this_row.NodeID[index]];
	node & node2 = ptrckt.nodes[this_row.NodeID[index + 1]];
	int lx = node1.x_coord;
	int rx = node2.x_coord + node2.width;
	set<int> related_nets;
	vector<pin>::iterator it;
	for(it = node1.pins.begin(); it != node1.pins.end(); ++it)
		related_nets.insert(it->pin2net);
	for(it = node2.pins.begin(); it != node2.pins.end(); ++it)
		related_nets.insert(it->pin2net);

	// Evaluate each possibility
	// Case 1:
	int best_order = 1;
	int local_HPWL = calculate_local_HPWL(ptrckt, related_nets);
	int best_HPWL = local_HPWL;
	
	// Case 2: 2.1.
	node2.x_coord = lx;
	node1.x_coord = rx - node1.width;
	local_HPWL = calculate_local_HPWL(ptrckt, related_nets);
	if(local_HPWL < best_HPWL)
	{
		best_HPWL = local_HPWL;
		best_order = 2;
	}

	switch(best_order)
	{
		case 1:
			node1.x_coord = lx;
			node2.x_coord = rx - node2.width;
			break;
		case 2:
			this_row.NodeID[index] = node2.ID;
			this_row.NodeID[index + 1] = node1.ID;
			break;
	}
	fixNet(ptrckt, node1);
	fixNet(ptrckt, node2);
	return best_order;
}

int bi_swap(ckt & ptrckt, tinyRow & this_row, node & node1, node & node2)
{
	int lx = node1.x_coord;
	int rx = node2.x_coord + node2.width;
	set<int> related_nets;
	vector<pin>::iterator it;
	for(it = node1.pins.begin(); it != node1.pins.end(); ++it)
		related_nets.insert(it->pin2net);
	for(it = node2.pins.begin(); it != node2.pins.end(); ++it)
		related_nets.insert(it->pin2net);

	// Evaluate each possibility
	// Case 1:
	int best_order = 1;
	int local_HPWL = calculate_local_HPWL(ptrckt, related_nets);
	int best_HPWL = local_HPWL;
	
	// Case 2: 2.1.
	node2.x_coord = lx;
	node1.x_coord = rx - node1.width;
	local_HPWL = calculate_local_HPWL(ptrckt, related_nets);
	if(local_HPWL < best_HPWL)
	{
		best_HPWL = local_HPWL;
		best_order = 2;
	}

	switch(best_order)
	{
		case 1:
			node1.x_coord = lx;
			node2.x_coord = rx - node2.width;
			break;
		case 2:
			this_row.NodeID[0] = node2.ID;
			this_row.NodeID[1] = node1.ID;
			break;
	}
	fixNet(ptrckt, node1);
	fixNet(ptrckt, node2);

	return best_order;
}


/* Find the best relative positions for three consecutive cells */
int tri_swap(ckt & ptrckt, tinyRow & this_row, int index)
{
	// Reference of the nodes
	node & node1 = ptrckt.nodes[this_row.NodeID[index]];
	node & node2 = ptrckt.nodes[this_row.NodeID[index + 1]];
	node & node3 = ptrckt.nodes[this_row.NodeID[index + 2]];
	int x1 = node1.x_coord;
	int x2 = node2.x_coord;
	int x3 = node3.x_coord;
	// Standard position of the nodes
	int lx = node1.x_coord;
	int rx = node3.x_coord + node3.width;
	int mutual_distance = (rx - lx - node1.width - node2.width - node3.width) / 2;
	// Add related nets to a set
	set<int> related_nets;
	vector<pin>::iterator it;
	for(it = node1.pins.begin(); it != node1.pins.end(); ++it)
		related_nets.insert(it->pin2net);
	for(it = node2.pins.begin(); it != node2.pins.end(); ++it)
		related_nets.insert(it->pin2net);
	for(it = node3.pins.begin(); it != node3.pins.end(); ++it)
		related_nets.insert(it->pin2net);
	// Evaluate each possibility
	int best_order;
	int best_HPWL;
	int local_HPWL;

	// Case 0: 1.2.3.
	local_HPWL = calculate_local_HPWL(ptrckt, related_nets);
	best_order = 0;
	best_HPWL = local_HPWL;
	
	// Case 1: 1.2.3.
	node1.x_coord = lx;
	node2.x_coord = lx + node1.width + mutual_distance;
	node3.x_coord = rx - node3.width;
	local_HPWL = calculate_local_HPWL(ptrckt, related_nets);
	if(local_HPWL < best_HPWL)
	{
		best_HPWL = local_HPWL;
		best_order = 1;
	}
	
	// Case 2: 1.3.2.
	node1.x_coord = lx;
	node3.x_coord = lx + node1.width + mutual_distance;
	node2.x_coord = rx - node2.width;
	local_HPWL = calculate_local_HPWL(ptrckt, related_nets);
	if(local_HPWL < best_HPWL)
	{
		best_HPWL = local_HPWL;
		best_order = 2;
	}
	
	// Case 3: 2.1.3.
	node2.x_coord = lx;
	node1.x_coord = lx + node2.width + mutual_distance;
	node3.x_coord = rx - node3.width;
	local_HPWL = calculate_local_HPWL(ptrckt, related_nets);
	if(local_HPWL < best_HPWL)
	{
		best_HPWL = local_HPWL;
		best_order = 3;
	}
	
	// Case 4: 2.3.1.
	node2.x_coord = lx;
	node3.x_coord = lx + node2.width + mutual_distance;
	node1.x_coord = rx - node1.width;
	local_HPWL = calculate_local_HPWL(ptrckt, related_nets);
	if(local_HPWL < best_HPWL)
	{
		best_HPWL = local_HPWL;
		best_order = 4;
	}
	
	// Case 5: 3.1.2.
	node3.x_coord = lx;
	node1.x_coord = lx + node3.width + mutual_distance;
	node2.x_coord = rx - node2.width;
	local_HPWL = calculate_local_HPWL(ptrckt, related_nets);
	if(local_HPWL < best_HPWL)
	{
		best_HPWL = local_HPWL;
		best_order = 5;
	}
	
	// Case 6: 3.2.1.
	node3.x_coord = lx;
	node2.x_coord = lx + node3.width + mutual_distance;
	node1.x_coord = rx - node1.width;
	local_HPWL = calculate_local_HPWL(ptrckt, related_nets);
	if(local_HPWL < best_HPWL)
	{
		best_HPWL = local_HPWL;
		best_order = 6;
	}

	switch(best_order)
	{
		case 0: // 1 2 3
			node1.x_coord = x1;
			node2.x_coord = x2;
			node3.x_coord = x3;
			return 0; // Do not need to fixNet since everything remains the same
		case 1: // 1 2 3
			node1.x_coord = lx;
			node2.x_coord = lx + node1.width + mutual_distance;
			node3.x_coord = rx - node3.width;
			break;
		case 2: // 1 3 2
			node1.x_coord = lx;
			node3.x_coord = lx + node1.width + mutual_distance;
			node2.x_coord = rx - node2.width;
			this_row.NodeID[index + 1] = node3.ID;
			this_row.NodeID[index + 2] = node2.ID;
			break;
		case 3: // 2 1 3
			node2.x_coord = lx;
			node1.x_coord = lx + node2.width + mutual_distance;
			node3.x_coord = rx - node3.width;
			this_row.NodeID[index] 	   = node2.ID;
			this_row.NodeID[index + 1] = node1.ID;
			break;
		case 4: // 2 3 1
			node2.x_coord = lx;
			node3.x_coord = lx + node2.width + mutual_distance;
			node1.x_coord = rx - node1.width;
			this_row.NodeID[index] 	   = node2.ID;
			this_row.NodeID[index + 1] = node3.ID;
			this_row.NodeID[index + 2] = node1.ID;
			break;
		case 5: // 3 1 2
			node3.x_coord = lx;
			node1.x_coord = lx + node3.width + mutual_distance;
			node2.x_coord = rx - node2.width;
			this_row.NodeID[index] 	   = node3.ID;
			this_row.NodeID[index + 1] = node1.ID;
			this_row.NodeID[index + 2] = node2.ID;
			break;
		case 6: // 3 2 1
			this_row.NodeID[index] 	   = node3.ID;
			this_row.NodeID[index + 2] = node1.ID;
			break;
	}
	fixNet(ptrckt, node1);
	fixNet(ptrckt, node2);
	fixNet(ptrckt, node3);

	return best_order;
}

/* Find the best relative positions for three consecutive cells */
int tri_swap(ckt & ptrckt, tinyRow & this_row, node & node1, node & node2, node & node3)
{
	// Reference of the nodes
	int x1 = node1.x_coord;
	int x2 = node2.x_coord;
	int x3 = node3.x_coord;
	// Standard position of the nodes
	int lx = node1.x_coord;
	int rx = node3.x_coord + node3.width;
	int mutual_distance = (rx - lx - node1.width - node2.width - node3.width) / 2;
	// Add related nets to a set
	set<int> related_nets;
	vector<pin>::iterator it;
	for(it = node1.pins.begin(); it != node1.pins.end(); ++it)
		related_nets.insert(it->pin2net);
	for(it = node2.pins.begin(); it != node2.pins.end(); ++it)
		related_nets.insert(it->pin2net);
	for(it = node3.pins.begin(); it != node3.pins.end(); ++it)
		related_nets.insert(it->pin2net);
	// Evaluate each possibility
	int best_order;
	int best_HPWL;
	int local_HPWL;

	// Case 0: 1.2.3.
	local_HPWL = calculate_local_HPWL(ptrckt, related_nets);
	best_order = 0;
	best_HPWL = local_HPWL;
	
	// Case 1: 1.2.3.
	node1.x_coord = lx;
	node2.x_coord = lx + node1.width + mutual_distance;
	node3.x_coord = rx - node3.width;
	local_HPWL = calculate_local_HPWL(ptrckt, related_nets);
	if(local_HPWL < best_HPWL)
	{
		best_HPWL = local_HPWL;
		best_order = 1;
	}
	
	// Case 2: 1.3.2.
	node1.x_coord = lx;
	node3.x_coord = lx + node1.width + mutual_distance;
	node2.x_coord = rx - node2.width;
	local_HPWL = calculate_local_HPWL(ptrckt, related_nets);
	if(local_HPWL < best_HPWL)
	{
		best_HPWL = local_HPWL;
		best_order = 2;
	}
	
	// Case 3: 2.1.3.
	node2.x_coord = lx;
	node1.x_coord = lx + node2.width + mutual_distance;
	node3.x_coord = rx - node3.width;
	local_HPWL = calculate_local_HPWL(ptrckt, related_nets);
	if(local_HPWL < best_HPWL)
	{
		best_HPWL = local_HPWL;
		best_order = 3;
	}
	
	// Case 4: 2.3.1.
	node2.x_coord = lx;
	node3.x_coord = lx + node2.width + mutual_distance;
	node1.x_coord = rx - node1.width;
	local_HPWL = calculate_local_HPWL(ptrckt, related_nets);
	if(local_HPWL < best_HPWL)
	{
		best_HPWL = local_HPWL;
		best_order = 4;
	}
	
	// Case 5: 3.1.2.
	node3.x_coord = lx;
	node1.x_coord = lx + node3.width + mutual_distance;
	node2.x_coord = rx - node2.width;
	local_HPWL = calculate_local_HPWL(ptrckt, related_nets);
	if(local_HPWL < best_HPWL)
	{
		best_HPWL = local_HPWL;
		best_order = 5;
	}
	
	// Case 6: 3.2.1.
	node3.x_coord = lx;
	node2.x_coord = lx + node3.width + mutual_distance;
	node1.x_coord = rx - node1.width;
	local_HPWL = calculate_local_HPWL(ptrckt, related_nets);
	if(local_HPWL < best_HPWL)
	{
		best_HPWL = local_HPWL;
		best_order = 6;
	}

	switch(best_order)
	{
		case 0: // 1 2 3
			node1.x_coord = x1;
			node2.x_coord = x2;
			node3.x_coord = x3;
			return 0; // Do not need to fixNet since everything remains the same
		case 1: // 1 2 3
			node1.x_coord = lx;
			node2.x_coord = lx + node1.width + mutual_distance;
			node3.x_coord = rx - node3.width;
			break;
		case 2: // 1 3 2
			node1.x_coord = lx;
			node3.x_coord = lx + node1.width + mutual_distance;
			node2.x_coord = rx - node2.width;
			break;
		case 3: // 2 1 3
			node2.x_coord = lx;
			node1.x_coord = lx + node2.width + mutual_distance;
			node3.x_coord = rx - node3.width;
			break;
		case 4: // 2 3 1
			node2.x_coord = lx;
			node3.x_coord = lx + node2.width + mutual_distance;
			node1.x_coord = rx - node1.width;
			break;
		case 5: // 3 1 2
			node3.x_coord = lx;
			node1.x_coord = lx + node3.width + mutual_distance;
			node2.x_coord = rx - node2.width;
			break;
		case 6: // 3 2 1
			break;
	}
	fixNet(ptrckt, node1);
	fixNet(ptrckt, node2);
	fixNet(ptrckt, node3);
	sort(this_row.NodeID.begin(), this_row.NodeID.end(), compareNodeID());

	return best_order;
}